from collections import deque
from typing import List


class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        m, n = len(maze), len(maze[0])

        def _is_valid(x, y):
            return 0 <= x < m and 0 <= y < n

        def _is_border(x, y):
            return x == 0 or x == m - 1 or y == 0 or y == n - 1

        def neighbors(x1, y1):
            return [(x2, y2) for (x2, y2) in [(x1 - 1, y1), (x1 + 1, y1), (x1, y1 - 1), (x1, y1 + 1)]
                    if _is_valid(x2, y2)]

        ans = 0
        queue = deque([entrance])
        visited = {(entrance[0], entrance[1])}
        while queue:
            ans += 1
            for _ in range(len(queue)):
                x0, y0 = queue.popleft()
                for x1, y1 in neighbors(x0, y0):
                    if maze[x1][y1] == ".":
                        if (x1, y1) not in visited:
                            queue.append([x1, y1])
                            visited.add((x1, y1))
                            if _is_border(x1, y1):
                                return ans
        else:
            return -1


if __name__ == "__main__":
    # 1
    print(Solution().nearestExit(maze=[["+", "+", ".", "+"],
                                       [".", ".", ".", "+"],
                                       ["+", "+", "+", "."]],
                                 entrance=[1, 2]))

    # 2
    print(Solution().nearestExit(maze=[["+", "+", "+"],
                                       [".", ".", "."],
                                       ["+", "+", "+"]], entrance=[1, 0]))

    # -1
    print(Solution().nearestExit(maze=[[".", "+"]], entrance=[0, 0]))

    print(Solution().nearestExit(maze=[["+", ".", "+", "+", "+", "+", "+"],
                                       ["+", ".", "+", ".", ".", ".", "+"],
                                       ["+", ".", "+", ".", "+", ".", "+"],
                                       ["+", ".", ".", ".", "+", ".", "+"],
                                       ["+", "+", "+", "+", "+", ".", "+"]], entrance=[0, 1]))
